package Leetcode.lc023;

import Leetcode.tools.ListNode;

import java.util.PriorityQueue;

/***
 * 合并K个有序列表，优先级队列(最小堆的使用)
 */
public class Sloution {
    public ListNode mergeKLists(ListNode[] lists) {
        /***
         * a,b已经是list实例，默认为头节点，直接比较头结点的值,注意判空
         */
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a,b)-> a.val-b.val);
        //初始化优先级队列
        for(ListNode i:lists){
            if(i!=null)
            heap.add(i);
        }
        ListNode dummy = new ListNode();
        ListNode cur=dummy;
        while (!heap.isEmpty()){
            ListNode poll = heap.poll();
            if(poll.next!=null){
                heap.offer(poll.next);
            }
            cur.next=poll;
            cur=cur.next;
        }
        return dummy.next;
    }
}
